package elementaryAlgorithm;

import sun.reflect.generics.tree.Tree;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;

/**
 * @author 郭辉
 * @className TODO
 * @description 107. 二叉树的层序遍历 II
 * 给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：root = [3,9,20,null,null,15,7]
 * 输出：[[15,7],[9,20],[3]]
 * 示例 2：
 *
 * 输入：root = [1]
 * 输出：[[1]]
 * 示例 3：
 *
 * 输入：root = []
 * 输出：[]
 *
 *
 * 提示：
 *
 * 树中节点数目在范围 [0, 2000] 内
 * -1000 <= Node.val <= 1000
 * 通过次数264,542提交次数365,499
 * @date 2023/4/6 15:40
 * @company 海康威视
 * @since 1.0.0
 */
public class Leet107 {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> res =new ArrayList<>();
        if (root == null){
            return res;
        }
        Queue<List<TreeNode>> queue = new LinkedList<>();
        Set<TreeNode> visited = new HashSet<>();

        List<TreeNode> first = new ArrayList<>();
        List<Integer> firstV = new ArrayList<>();
        first.add(root);
        queue.add(first);
        visited.add(root);
        firstV.add(root.val);
        res.add(firstV);

        while (!queue.isEmpty()){
            List<TreeNode> poll = queue.poll();
            List<TreeNode> temp = new ArrayList<>();
            List<Integer> temList = new ArrayList<>();
            for (int i = 0; i < poll.size(); i++) {
                TreeNode node = poll.get(i);
                if (node.left != null){
                    temp.add(node.left);
                    temList.add(node.left.val);
                    visited.add(node.left);
                }
                if (node.right != null){
                    temp.add(node.right);
                    temList.add(node.right.val);
                    visited.add(node.right);
                }
            }
            if (!temp.isEmpty()){
                queue.add(temp);
                res.add(temList);
            }
        }
        //倒序
        Collections.reverse(res);
        return res;

    }

    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(2);
        TreeNode node3 = new TreeNode(4);
        TreeNode node4 = new TreeNode(5);
        TreeNode node2 = new TreeNode(3,node3,node4);
        TreeNode root = new TreeNode(1,node1,node2);

        Leet107 leet107 = new Leet107();
        System.out.println(leet107.levelOrderBottom(null));
    }
}
